\vspace{-0.15in}
\section{Introduction}
\vspace{-0.15in}
%Push process. Feige et al. Panconesi. Giakopoulos.
%Berenbrink. Sauerwald. Censor-Hillel.

% Description of Problem?nodes
We study a distributed propagation mechanism in networks, called the
{\em coalescing-branching random walk} ({\em cobra walk}, for short).
A cobra walk is a variant of the standard random walk, and is
parameterized by a {\em branching factor}, $k$.  The process starts
from an arbitrary node, which is initially labeled {\em active}.  For
instance, this could be a node that has a piece of data, rumor, or a
virus. In a cobra walk, for each discrete time step, each active node chooses $k$
random neighbors (sampled independently with replacement) to become
active for the next step; this is the ``branching" property, in which
each node spawns multiple independent random walks.  A node is active
for step $t$ if and only if it is chosen by an active node in step
$t-1$; this is the ``coalescing" property, i.e., if multiple walks
meet at a node, they coalesce into one walk.

A cobra walk generalizes the standard random
walk~\cite{lovasz-survey,upfal}, which is equivalent to a cobra walk
with $k = 1$.  Random walks on graphs have a wide variety of
applications, including being fundamental primitives in distributed
network algorithms for load balancing, routing, information
propagation, gossip, and
search~\cite{DNP09-podc,DNPT10-podc,BBSB04,ZS06}.  Being local and
requiring little state information, random walks and their variants
are especially well-suited for self-organizing dynamic networks such
as Internet overlay, ad hoc wireless, and sensor networks~\cite{ZS06}.
As a propagation mechanism, one parameter of interest is the {\em
cover time}, the expected time it takes to cover all the nodes in a
network.  Since the cover time of the standard random walk can be
large --- $\Theta(n^3)$ in the worst case, $\Theta(n \log n)$ even for
expanders \cite{lovasz-survey} --- some recent studies have studied
simple adaptations of random walks that can speed up cover
time~\cite{AHKV03,berenbrink,DP05}.  Our analysis of cobra walks
continues this line of research, with the aim of studying a
lightweight information dissemination process that has the potential
to improve cover time significantly.

Our primary motivation for studying cobra walks is their close
connection to SIS-type epidemic processes in networks.  The SIS
(standing for Susceptible-Infected-Susceptible) model
(e.g., \cite{durrett2010some}) is widely used for capturing the spread
of diseases in human contact networks or propagation of viruses in
computer networks.  Three basic properties of an SIS process are: (a)
a node can infect one or more of its neighbors (``branching"
property); (b) a node can be infected by one or more of its neighbors
(``coalescence" property) and (c) an infected node can be cured and
then become susceptible to infection at a later stage.  Cobra walks
satisfy all these properties, while standard random walks and other
gossip-based propagation mechanisms violate one or more.  Also, while
there has been considerable work on the SIS model
(\cite{ganesh2005effect,van2011n, givan2011predicting,
durrett2010some, parshani2010epidemic, draief2011random,
berger2005spread}), it has been analytically hard to tackle basic {\em
coverage} questions: (1) How long will it take for the epidemic to
infect, say, a constant fraction of network? (2) Will every node be
infected at some point, and how long will this take?  Our analysis of
cobra walks in certain special graph classes is a step toward a better
understanding of such questions for SIS-type processes.

\vspace{-0.15in}
\subsection{Our results and techniques}
\vspace{-0.1in}
\label{sec:results}
We derive near-tight bounds on the cover time of cobra walks on trees,
grids, and expanders.  These special graph classes arise in many
distributed network applications, especially in the modeling and
construction of peer-to-peer (P2P), overlay, ad hoc, and sensor
networks.  For example, expanders have been used for modeling and
construction of P2P and overlay networks, grids and related graphs
have been used as models for ad hoc and sensor networks, and spanning
trees are often used as backbones for various information propagation
tasks.

We begin with an observation that Matthew's Theorem \cite{matthews1988covering, lovasz-survey} for random walks
extends to cobra walks; that is, the cover time of a cobra walk on an
$n$-node graph is at most $\ln n$ times the maximum hitting time of a
node; for many graphs, this is also a tight bound.  This enables us to
focus on deriving bounds for the hitting time.

We face two technical challenges in our analysis.  First, unlike in a
standard random walk, cobra walks have multiple ``active'' nodes at
any step, and in almost all graphs, it is difficult to characterize
the distribution of the active nodes at any point of time.  Second,
the combination of the branching and coalescing properties introduces
a non-trivial dependence among the active nodes, making it challenging
to quantify the probability that a given node is made active during a
given time period.  Surprisingly, these challenges manifest even in
tree networks.  We present a result that gives tight bound on the cover time
for trees, which we obtain by establishing a recurrence relation for
the expected time taken for the cobra walk to cross an edge along a
given path of the tree.
\begin{itemize}
\item For an arbitrary $n$-node tree, a cobra walk with $k \ge 2$
  covers all nodes in $O(n \log n)$ steps with high
  probability (w.h.p., for short)\footnote{By the term ``with high probability'' (w.h.p., for
  short) we mean with probability $1 - 1/n^c$, for some constant $c >
  0$.} (Theorem~\ref{tree:main_result} of
  Section~\ref{sec:trees}).
\end{itemize}
For a matching lower bound, we note that the cover time of a cobra
walk in a star graph is $\Omega(n \log n)$ w.h.p.  We
conjecture that the cover time for {\em any $n$-node graph}\/ is $O(n
\log n)$.  By exploiting the regular
structure of a grid, we establish improved and near-tight bounds for
the cover time on $d$-dimensional grids.
\begin{itemize}
\item
For a $d$-dimensional grid, we show that a cobra walk with $k \ge d$
takes $O(n^{1/d} \log n)$ steps, w.h.p.  (cf. Theorem~\ref{the:grid} of 
Section~\ref{sec:grid}).
\end{itemize}
Our main technical result is an analysis of cobra walks on expanders,
which are graphs in which every set $S$ of nodes of size at most half
the number of vertices has at least $\alpha |S|$ neighbors for a
constant $\alpha$, which is referred to as the expansion factor.
\begin{itemize}
\item
We show that for an $n$-node constant-degree expander, a cobra walk
covers a constant fraction of nodes in $O(\log n)$ steps and all the
nodes in $O(\log^2 n)$ steps w.h.p.
assuming that either the
branching factor or the expansion factor is sufficiently large
(cf. Theorems \ref{exp:phaseI} and \ref{exp:phaseII} of Section~\ref{sec:exp}).
\end{itemize}
Our analysis for expanders proceeds in two phases.  We show that in
the first phase, which consists of $O(\log n)$ steps, the branching
process dominates resulting in an exponential growth in the number of
active nodes until a constant fraction of nodes become active, with
high probability.  In the second phase, though a large fraction of the
nodes continues to be active, dependencies caused by the coalescing
property prevent us from treating the process as multiple independent
random walks, analyzed in~\cite{AAKKLT} (or even $d$-wise independent
walks for a suitably large $d$).  We overcome this hurdle by carefully
analyzing these dependencies and bounding relevant conditional
probabilities, and define a time-inhomogeneous Markov process that is
stochastically dominated by the cobra walk in terms of coverage.  We
then use the notion of merging conductance and the machinery
introduced in~\cite{mihail1989conductance} to analyze
time-inhomogeneous Markov chains, and establish an $O(\log n)$ bound
w.h.p. on the maximum hiting time, leading to an $O(\log^2 n)$ bound
on the cover time.

\junk{
we show a cover time of $O(n \log n)$ (cf. Theorem \ref{}), which can
be improved to a cover time of $\Theta(n)$ for the line. For a
$d$-dimensional grid, we show a cover time of $O(n^{1/d} \log n)$
(cf. Theorem \ref{}). To show these results, we derive an analogue of
Matthew's bound for cobra walks that holds also in general
graphs. This bound upper bounds the cover time of a cobra walk to its
maximum hitting time. Our results hold for branching factor $k \geq
2$. We note that these bounds are essentially optimal, since diameter
is trivial lower bound on the cover time. (In general, we note these
bounds are asymptotically much smaller compared to the cover time of
the (standard) random walk which is cobra walk with $k=1$ \footnote{It
  is not surprising that increasing branching factor deceases the
  cover time, but the amount of decrease seems to depend on the
  expansion properties of the underlying graph.}. For example, the
cover time of random walk on a line is $\Theta(n^2)$, which is
quadratically larger compared to cobra walk.)
\item 
 We show that the partial cover time of a cobra walk in an $n$-node
 constant-degree expander is $O(\log n)$ and the cover time is
 $O(\log^2 n)$ with high probability (cf. Thoerems \ref{} and
 \ref{}). In a clique, we show that the cover time of a cobra walk is
 $O(\log n)$.  Our results hold even for $k = 2$ (assuming
 sufficiently large expansion). (We note that the cover time of
 standard random walk is $\Theta(n \log n)$ in an expander.) Our cover
 time bound also implies that the total number of messages sent is
 $O(n \log n)$ for partial coverage and $O(n \log^2 n)$ for full
 coverage.  We note that this message complexity is essentially
 optimal and is within a logarithmic factor compared to the cover time
 of the standard random walk. Thus, increasing the branching factor to
 just 2 in every time step, yields an exponential speedup compared to
 branching factor 1, while not increasing the total message complexity
 by too much.


\end{itemize}


The branching
property of a cobra walk makes

{\em cover time}, which is
the the number of steps for the walk to reach all the nodes and the
{\em $\delta$-cover time}, which is the number of steps needed for the
walk to reach at least a $\delta$ fraction of the nodes. 

Due to the
coalescing property, cobra walks are harder to analyze than random
walks or multiple independent parallel random walks \cite{alon-etal}
(cf. Section \ref{}).  On the other hand, the coalescing property and
small (constant) branching factor ensures that each node sends at most
a constant number of messages per step which makes the process
lightweight.
}
\junk{
This results in a
stochastic process in the underlying network which has interesting
properties significantly different from both the standard random walk
(which is equivalent to cobra walk with branching factor $k=1$) as
well as other gossip-based information spreading mechanisms such as
the ``push'' process. (see Section \ref{sec:related}).



A well-studied randomized information propagation process in networks
is the (standard) {\em random walk}. In a random walk, in each step,
the current node (the one that has the piece of information) chooses a
random neighbor to pass the information. The study of random walks on graphs has a rich history, and we refer
the reader to~\cite{lovasz-survey,upfal} for a survey. Random walk is a fundamental
primitive useful in a wide variety of network applications ranging
from token management and load balancing to search, routing,
information propagation, gathering, and gossip
(e.g.,\cite{DNP09-podc,DNPT10-podc,BBSB04,ZS06} and the references
therein).  Random walks are local and lightweight and require little
index or state maintenance which make them especially attractive to
. An important parameter of interest in a
random walk is the {\em cover time} --- the (expected) number of
rounds needed till the walk visits all the nodes in the network.
Random walks are resource efficient in the sense that there is
only a single ``active" node holding the information at any step; thus
only constant work (i.e., communication or number of messages
transmitted) is performed per round in a random walk.  However, the
price is the cover time can be quite high in general --- $\Theta(n^3)$
in the worst case (see e.g., \cite{lovasz-survey}). In fact, even in
{\em expander graphs}, an important class of graphs which have good
connectivity and expansion properties and arise in a number of network applications
(see e.g., \cite{Wigderson-exsurvey}), the cover time is polynomially large
--- $\Theta(n \log n)$ \cite{lovasz-survey}. Hence, several recent
works have addressed the issue of speeding up the cover time of random
walks~\cite{AHKV03,berenbrink,DP05}. In many of these works the main
approach to speed up is by slightly modifying the random walks ---
e.g., visiting additional (constant) number of neighbors of the
current node, while proceeding with the random walk as usual.  The
typical speedup given by these approaches is not very large, the cover
time remains still polynomial. In particular, in expander graphs the
speed up is by a logarithmic factor~\cite{berenbrink}. This raises the
question whether we can speed up random walks significantly (at least
in important classes such as expanders), by modifying the
process. This is one  motivation of the current paper.  

A second motivation comes from understanding the propagation speed of
certain epidemic processes in networks.  Epidemic processes, such as
SIS (Susceptible-Infected-Susceptible \cite{}), have been used to
study spread of diseases in social networks or propagation of viruses
in computer networks. Two basic properties that these processes
possess are: (1) a node can infect one or more of its neighbors
(``branching" property); and (2) a node can be infected by one or more
of its neighbors (``coalescence" property) and (3) an infected node
can be cured and be susceptible to infection at a later stage.
Standard random walks and other gossip-based propagation mechanisms
(cf. Section \ref{}) are not suitable for modeling and analyzing such
epidemic processes. It has been analytically hard to tackle basic {\em
  coverage} questions in SIS-type epidemic processes such as: 1) How
long will it take for the epidemic to infect, say, a constant fraction
of network; 2) Will every node be infected at some point, and how long
will this take? There have been some results (especially in continuous
settings --- cf. Section \ref{}) on SIS and related processes, but to
the best of our knowledge there is no known work that rigorously
analyzes the coverage {\em time} taken by SIS-type epidemic processes.

We present techniques for analyzing cover time of cobra walks in
various graph classes.  We derive almost-tight bounds on cover time of
cobra walk in important graph classes including expander graphs,
trees, grids, and cliques.  These graphs arise in many distributed
network applications, especially in the modeling and construction of
peer-to-peer (P2P), overaly, ad hoc, and sensor networks.  For
example, expanders have been used for modeling and construction of P2P
and overlay networks, and grids and related graphs have been used as
models for ad hoc and sensor networks.  We state our specific results
for various graph classes below (throughout $n$ is the number of nodes
in the network):
\begin{itemize}
\item For an arbitrary  tree we show a cover time of $O(n \log n)$ (cf. Theorem \ref{}), which can be improved to a cover time of $\Theta(n)$ for the line. For a $d$-dimensional grid, we show a cover time of $O(n^{1/d} \log n)$ (cf. Theorem \ref{}). To show these results, we derive an analogue of  Matthew's bound  for cobra walks that holds also in general graphs. This bound upper bounds the cover time of a cobra walk to its maximum hitting time. Our results hold
for branching factor $k \geq 2$. We note that these bounds are essentially optimal, since diameter is trivial lower
bound on the cover time. (In general, we note these bounds are asymptotically much smaller compared to the cover time of the (standard) random walk  which is cobra walk with $k=1$ \footnote{It is not surprising that increasing branching factor deceases the cover time, but the amount of decrease
seems to depend on the expansion properties of the underlying graph.}. For example, the cover time of random walk on a line is $\Theta(n^2)$, which
is quadratically larger compared to cobra walk.) 
\item 
 We show that the partial cover time of a cobra walk    in an $n$-node constant-degree expander  is $O(\log n)$  and the cover time is
$O(\log^2 n)$   with high probability (cf. Thoerems \ref{} and \ref{}). In a clique, we show that the cover time of a cobra walk is $O(\log n)$.
 Our results hold even for $k = 2$ (assuming sufficiently large expansion). (We note that the cover time of standard random walk   is $\Theta(n \log n)$ in an expander.) Our cover time bound also implies that the total number of messages sent is $O(n \log n)$  for
partial coverage and $O(n \log^2 n)$ for full coverage.  We note that this message complexity is essentially optimal and is within a logarithmic factor compared to the cover time of the standard random walk. Thus, increasing the branching factor to just 2 in every time step, yields an exponential speedup compared to branching factor 1, while not increasing the total message complexity by too much.
\end{itemize}
%This can be a thought of a type
%of  {\em two choices} paradigm (\cite{balanced}) applying in the context of random walks in networks. 
}

\iffalse
 A main result of the paper is the cover time for graphs of suitably large expansion. Here we define a $\Delta$-regular graph $G$ to be an expander if every subset S of nodes of size $\leq \delta n$ has at least $\alpha |S|$ neighbors, where the neighborhood of $S$ can include members of $S$ as well. 

We show that for $\alpha$ sufficiently large and for $k \geq 1 + \ln (2\Delta / \alpha - 1)$, a cobra walk on expander $G$ with branching factor k will cover $\Omega(n)$ nodes of $G$ in $O(\log n)$ steps. We then show that a k-factor cobra walk on $G$ will cover the entire graph in $O(\log^2 n)$ steps. 
\fi

%By varying the branching factor
%and the time that a node remains infected, the process can also be
%viewed as a generalized rumor spreading model, with applications in
%both epidemiology and information dissemination.
\iffalse
We next compare  cobra walks and the implications of our results with other related randomized information spreading processes in networks.
We then discuss potential  scenarios where study of cobra walks can be useful.


We believe that our  results can also be generalized to understand
the time taken for an epidemic process in an SIS-type model to spread
in a network~\cite{GANESH,KES,PIET}.  By varying the branching factor
and the time that a node remains infected, the process can also be
viewed as a generalized rumor spreading model, with applications in
both epidemiology and information dissemination.

While the persistence time and
epidemic density of SIS-type epidemic models are well
studied~\cite{GANESH,KES}, here we analyze the time needed for a
SIS-type process to affect a constant fraction of the network.

In this paper, we study a new gossip model that we believe better
models several spreading phenomena.  Our model is best captured by the
following ``branching process'' on a finite graph $G$.  Let $S_t$
denote the set of active nodes in $G$, with $S_0$ being the initial
set of active nodes (usually this is a singleton set).  In round $t$,
each node in $S_{t-1}$ selects $k$ nodes uniformly at random (say,
with replacement) from its set of neighbors; $S_t$ is the union of all
the nodes selected in round $t$.  We focus on two questions: 

how long does it take for the information to reach a constant fraction
of the nodes?

how long does it take for the information to reach all the nodes?

It is instructive to consider the cases of $k = 1$ and $k = 2$.  The
case $k = 1$ is precisely a random walk in the graph, and we need not
discuss it further.  It is not hard to see that the case $k = 2$ will
eventually cover all the nodes; it is interesting to see how it
compares with the standard push process.  The standard push process
takes linear time to complete on the line graph.  The branching
process, however, will take $\Theta(n^2)$ to complete.

\fi



\iffalse
\vspace{-0.15in}
\subsection{Our results} 
\vspace{-0.1in}
We analyze the partial and full cover times of branching random walks
on bounded-degree regular expanders.  We say that a graph is an
$(\alpha,\delta)$-expander if the number of neighbors of every node 
set $S$ of nodes of size at most $\delta n$ is at least
$\alpha|S|$.  (Note that the neighbors of nodes in $S$ may include
nodes in $S$.)

\begin{itemize} 
\item We show that for any $\Delta$-regular $n$-node  $(\alpha,
  \delta)$-expander, the $k$-branching random walk covers at least
  $\delta n$ nodes in $O(\log n)$ steps for $k \ge 1 +
  \ln(2\Delta/(\alpha-1))$ assuming $\alpha$ is sufficiently large.
  In particular, for any random regular graph, the 2-branching random
  walk covers $\Omega(n)$ nodes in $O(\log n)$ steps with high
  probability.

\item We show that the cover time of a $k$-branching random walk on
  any bounded-degree regular $(\Omega(n), \alpha)$-expander graph is
  $O(\log^2 n)$ for $k \ge 1 + \ln(2\Delta/(\alpha-1))$, assuming
  $\alpha$ is sufficiently large.  In particular, the cover time of
  the 2-branching random walk on any random regular graph with
  constant degree is $O(\log^2 n)$.
\end{itemize}
\junk{We also extend the analysis of partial coverage to the SIS model.
\begin{itemize}
\item
If the ratio of the infection rate to the cure rate is sufficiently
high and the epidemic persists, then the epidemic reaches a constant
fraction of the nodes in $O(\log n)$ steps, with high probability.
\end{itemize}}

\fi

\vspace{-0.15in}
\subsection{Related work and comparison}
\vspace{-0.1in}
\noindent{\bf Branching and coalescing processes.} There is a large
body of work on branching processes (without coalescence) on various
discrete and non-discrete
structures~\cite{MR0163361,Madras1992255,benjamini2010trace}. A study
of coalescing random walks (without branching) was performed in
~\cite{cooper2012coalescing} with applications to voter models.
Others have looked at processes that incorporate branching and
coalescing particle
systems~\cite{arthreya2005branching,sun2008brownian}. However, these
studies treat the particle systems as continuous-time systems, with
branching, coalescing, and death rates on restricted-topology
structures such as integer lattices. To the best of our knowledge,
ours is the first work that studies random walks that branch and
coalesce in discrete time and on various classes of non-regular finite
graphs.
\smallskip

\noindent{\bf Random walks and parallel random walks.}
% Bounds in
%terms of spectral properties of graphs and tighter bounds for
%arbitrary graphs were obtained in~\cite{broder-karlin,chandra,feige}. 
Feige \cite{feige1,feige2} showed that the cover time of a random walk on any
undirected $n$-node  connected graph is  between $\Theta(n \log n)$ and $\Theta(n^3)$ with both the lower and upper bounds being achieved in certain graphs. With the rapidly increasing interest in information (rumor) spreading processes in
large-scale networks and the gossiping paradigm (e.g., see \cite{sicomp} and the references therein), there have been a
number of studies on speeding up the cover time of random walks on graphs.  One of the earliest
studies is due to Adler et al~\cite{AHKV03}, who studied a process on
the hypercube in which in each round a node  is chosen uniformly at
random and covered; if the chosen node  was already covered, then an
uncovered neighbor of the node is chosen uniformly at random and
covered.  For any $d$-regular graph, Dimitrov and Plaxton showed that
a similar process achieves a cover time of $O(n + (n \log
n)/d)$~\cite{DP05}.  For expander graphs, Berenbrink et al\ showed a
simple variant of the standard random walk that achieves a linear (i.e., $O(n)$)
cover time~\cite{berenbrink}.

It is instructive to compare cobra walks with other mechanisms to
speed up random walks as well as with gossip-based rumor spreading
mechanisms.  Perhaps the most related mechanism is that of parallel
random walks which was first studied in~\cite{broder} for the special
case where the starting nodes are drawn from the stationary
distribution, and in~\cite{AAKKLT} for arbitrary starting nodes.
Nearly-tight results on the speedup of cover time as a function of the
number of parallel walks have been obtained by~\cite{ElsasserS09} for
several graph classes including the cycle, $d$-dimensional meshes,
hypercube, and expanders.  (Also see~\cite{ER09} for results on mixing
time.)  Though cobra walks are similar to parallel random walks in the
sense that at any step multiple nodes may be selecting random
neighbors, there are significant differences between the two
mechanisms.  First the cover times of these walks are not comparable.
For instance, while $k$ parallel random walks may have a cover time of
$\Omega(n^2/\log k)$ for any $k \in [1,n]$~\cite{ElsasserS09}, a
$2$-branching cobra walk on a line has a cover time of $O(n)$.
Second, while the number of active nodes in $k$ parallel random walks
is always $k$, the number of active nodes in any $k$-branching cobra
walk is continually changing and {\em may not even be monotonic}.
Most importantly, the analysis of cover time of cobra walks needs to
address several dependencies in the process by which the set of active
nodes evolve; we use the machinery of time-inhomogenous Markov chains
to obtain the cover time bound for bounded-degree expanders (see
Section~\ref{sec:exp}).

The works of \cite{DNP09-podc,DNPT10-podc} presented distributed
algorithms for performing a standard random walk in sublinear time,
i.e., in time sublinear in the length of the walk.
\junk{
They present goal is to improve the round complexity of the standard
walk --- which takes $\ell$ rounds for a walk of length $\ell$.  The
inear time distributed algorithm for performing random walks whose
time complexity is sublinear in the length of the walk.  } In
particular, the algorithm of \cite{DNPT10-podc} performs a random walk
of length $\ell$ in $\tilde{O}(\sqrt{\ell D})$ rounds w.h.p. on an
undirected network, where $D$ is the diameter of the network.
%The high-level idea behind the algorithm is to perform
%several short walks in parallel and then stitch them carefully.   
However, this speed up comes with a drawback: the message complexity
of the above faster algorithm is much worse compared to the naive
sequential walk which takes only $\ell$ messages.  In contrast, we
note that the speedup in cover time given by a cobra walk over the
standard random walk comes only at the cost of a slightly worse
message complexity.

\smallskip
\noindent {\bf Gossip-based mechanisms.} 
Gossip-based information propagation mechanisms have also been used
for information (rumor) spreading in distributed networks.
%Gossip-based algorithms have also been successfully to {\em design} efficient
%distributed algorithms for a variety of problems in networks such as
%information dissemination, aggregate computation, constructing overlay
%topologies.
%Such local algorithms are considered natural mathematical  models of how spreading
%occurs in real-world networks. 
In the most typical rumor spreading models, gossip involves either a
push step, in which nodes that are aware of a piece of information
 (being disseminated) pass it to random neighbors, or a pull step, in
 which nodes that are unaware of the information attempt to extract
 the information from one of their randomly chosen neighbors, or some
 combination of the two.  In such models, the knowledgeable nodes or
 the ignorant nodes participate in the dissemination problem in {\em
 every} round (step) of the algorithm.  \junk{ Rumor spreading and
 related gossip-based processes have been extensively analyzed in
 recent years (see e.g., \cite{panconesi1, panconesi2, panconesi3,
 gia1, gia2, pana1, pana2} and the references therein).} The main
 parameter of interest in many of these analyses is the number of
 rounds needed till all the nodes in the network get to know the
 information.
%It is known that in any graph, rumor spreading takes $O(n \log n)$ rounds.

The rumor spreading mechanism that is most closely related to cobra
walks is the basic push protocol, in which in every step every
informed node selects a random neighbor and pushes the information to
the neighbor, thus making it informed.  Feige et al. \cite{feige-rumor}
show that the push process completes in every undirected graph in
$O(n \log n)$ steps, with high probability.  Since then, the push
protocol and its variants have been extensively analyzed both for
special graphs, as well as for general graphs in terms of their
expansion properties (see e.g., \cite{panconesi1, panconesi2,
panconesi3, gia1, gia2, pana1, pana2}).  Again, though cobra walk and
push-based rumor spreading share the property that multiple nodes are
active in a given step, the two mechanisms differ significantly.
While the set of active nodes in rumor spreading is monotonically
nondecreasing, this is not so in cobra walks, an aspect that makes the
analysis challenging especially with regard to full coverage.
Furthermore, the message complexity of the push protocol can be
substantially different than that of cobra.  A simple example is the
star network, which the push protocol covers in $\Theta(n \log n)$
steps with a message complexity of $\Theta(n^2 \log n)$, while the
$2$-branching cobra walk has both cover time and message complexity
$\Theta(n \log n)$.  This can be extended to show similar results for
star-based networks that have been proposed as models for
Internet-scale networks~\cite{star-internet}.

%\smallskip
\vspace{-0.15in}
\subsection{Potential applications}
 \vspace{-0.1in} 
As mentioned at the outset, cobra walks are closely related to SIS
model in epidemics, but they may be easier to analyze using tools from
random walk and Markov chain analyses.  While the persistence time and
epidemic density of SIS-type epidemic models are well
studied~\cite{GANESH,KES,PIET}, to the best of our knowledge the time
needed for a SIS-type process to affect a large fraction (or the
whole) of the network has not been well-studied.  Our results and
analyses of cobra walks on more general networks can be useful in
predicting the time taken for a real epidemic process following an
SIS-type model to spread in a network~\cite{GANESH,KES,PIET}.
\junk{Our
analysis of cover time and partial cover time may be generalized to
understand the time taken for an epidemic process in an SIS-type model
to spread in a network.}
%While the persistence time and epidemic
%density of SIS-type epidemic models are well studied, here we analyze
%the time needed for a SIS-type process to reach partial coverage of a
%graph.  

Cobra walks can also serve as a lightweight information dissemination
protocol in networks, similar to the push protocol. As pointed out
earlier, in certain types of networks, the message complexity incurred
by a cobra walk to cover a network can be smaller than that for the
push protocol.  This can be useful, especially in infrastructure-less
anonymous networks, where nodes don't have unique identities and and
may not even know the number of neighbors.  In such networks, it is
difficult to detect locally when coverage is completed\footnote{In
networks with identities and knowledge of neighbors, a node can
locally stop sending messages when all neighbors have the rumor. This
reduces the overall message complexity until cover time.}.  If nodes
have a good upper bound on $n$ (the network size), however, then nodes
can terminate the protocol after a number of steps equal to the
estimated cover time.  In such a scenario, message complexity is also
an important performance criterion.





